package leetcode每日一题;

/**
 * 1. 问题描述
 *      给定一个正整数，找到比这个正整数小的最大的单调递增数
 *
 * 2， 算法分析
 *      1. 暴力法
 *
 *
 *
 * 3， 代码实现
 */
@SuppressWarnings("all")
public class 单调递增的数字 {
    public static void main(String[] args) {
        String s = "124";

    }


    /**
     *  假设当前数字为 332，我们如何找到比这个数小的最大的单调递增的数字
     *  3 3 2  由于我们需要找到一个尽可能大的数，此时可能会考虑贪心算法
     *  每一位上的数字尽可能大，对于个位上的数字我们
     *  434 我们从最高位百位上的数字看，当前为4，而后面的最小值为3，所以此时百位的最大值为3
     *  在确定百位最大9，最大9
     *  53215        53219
     *  153201   99999(最大)因为有0出现，此时最高位只能位0，所以取其他位置最大即可
     *  1234109  4109 --->
     *  11110    11109
     *
     * @param N
     * @return
     */
    public static int monotoneIntcreasingDigits(int N) {
        if (N >= 0 && N <= 9) {return N;}
        String s = N + ""; // 将 int ---> String
        int[] temp = new int[s.length()]; // 存放N的每一位
        for (int i = 0; i < s.length(); i++) {
            temp[i] = s.charAt(i) + 0; // 自动转型 char ---> int
        }
        // 此时temp数组中存放的是N的每一位从最高位到最低位
        int ans = 0;
        for(int i = 0; i < temp.length-1; i++) {
            if (temp[i] > temp[i+1]) { // 由于此时为严格大于号此时temp[i]不可能为0，是一个严格大于0
                // 找到当前第i+1个数字到最后数字中最小的一位
                // 判断当前i时候指向倒数第2个数字
                if (i == temp.length - 2) { // 如果当前数字位倒数第2位
                    // 此时的最小值就是最后一位
                    // 12341 ---> 12339
                    // 判断当前最小值是否为0
                    // 如果为0    12340 ---> 12339
                    if (temp[i+1] == 0) {
                        temp[i] = temp[i] - 1; // 贪心
                        temp[i+1] = 9; // 贪心
                    } else {
                        // 如果不为0   12341 ---> 12339
                        temp[i] = temp[i-1]; // 贪心
                        temp[i+1] = 9; // 贪心
                    }
                } else {

                }
            }
        }
        return N; // 说明当前数字就是一个单调递增的数字
    }

    public static int test(int N) {
        char[] strN = Integer.toString(N).toCharArray();
        int i = 1;
        while (i < strN.length && strN[i - 1] <= strN[i]) {
            i += 1;
        }
        if (i < strN.length) {
            while (i > 0 && strN[i - 1] > strN[i]) {
                strN[i - 1] -= 1;
                i -= 1;
            }
            for (i += 1; i < strN.length; ++i) {
                strN[i] = '9';
            }
        }
        return Integer.parseInt(new String(strN));
    }



    /**
     * 暴力法   超时  当数字大于等于963856657时，leetcode平台的抛出超出时间限制
     * 所以此解法只适用于数字比较小的时候
     * @param N
     * @return
     */
    public static int monotoneIncreasingDigits(int N) {
        if(N <= 9 && N >= 0) {return N;} // 特殊的边界情况
        int i = N;
        while (i >= 0) {
            if (support(i)) {
                return i;
            }
            i--;
        }
        return -1;
    }

    // 判断当前数字是否为单调递增的数字
    public static boolean support(int num) {
        if (num >= 0 && num <= 9) {return true;}
        String temp = num + ""; // 将整形转化为字符串类型
        for (int i = 0; i < temp.length() - 1; i++) {
            if (temp.charAt(i) > temp.charAt(i+1)) {
                return false;
            }
        }
        return true;
    }
}